package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.List;

/** 
* @ClassName   : Leetcode089 
* @author      : ganwei 
* @date        : 2020年5月8日 
* @Description : 89. 格雷编码 
*/
public class Leetcode0089 {
	List<Integer> result = new ArrayList<>();
    /**
     * -这题必须还是牛哄哄的回溯打法
     */
	public List<Integer> grayCode(int n) {
		result.add(0);
		if(n == 0){
			return result;
		}
		int head = 1;
		for(int i = 0; i < n; i++){
			for(int j = result.size()-1; j>=0; j--){
				result.add(head+result.get(j));
			}
			head <<= 1;
		}
		return result;
    }

    

	
    public static void main(String[] args) {
    	Leetcode0089 l089 = new Leetcode0089();
    	l089.grayCode(3);
    	for(Integer i : l089.result) {
    		System.out.println(i);
    	}

    	
    }
}
